class Solution {
    public int countNodes(TreeNode root) {
        TreeNode node = root;
        int level = 0;
        while (node != null)
        {
            level++;
            node = node.left;
        }
        if (level <= 1) return level;
        int left = 1 << (level - 1);
        int right = 1 << (level);
        int ans = left;
        int mid;
        while (left < right)
        {
            mid = left + ((right - left) >> 1);
            if (check(root, mid, level)) {
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return ans;
    }
    public boolean check(TreeNode root, int id, int level)
    {
        int bit = 1 << (level - 2);
        while (bit > 0)
        {
            if ((bit & id) == 0) { root = root.left; }
            else { root = root.right; }
            bit >>= 1;
        }
        return root != null;
    }
}